Mrówki i biedronka
Limit pamięci: 32 MB
Jak wiadomo, mrówki potrafią "hodować" mszyce.
Mszyce wydzielają słodką rosę miodową, którą spijają mrówki.
Mrówki zaś bronią mszyc przed ich największymi wrogami - biedronkami.
Na drzewie obok mrowiska znajduje się
właśnie taka hodowla mszyc.
Mszyce żerują na liściach oraz w rozgałęzieniach drzewa.
W niektórych z tych miejsc znajdują się również mrówki patrolujące
drzewo.
Dla ustalenia uwagi, mrówki są ponumerowane od jeden w górę.
Hodowli zagraża biedronka, która zawsze siada na drzewie tam,
gdzie są mszyce, czyli
na liściach lub w rozgałęzieniach.
W chwili, gdy gdzieś na drzewie usiądzie biedronka, mrówki patrolujące
drzewo ruszają w jej stronę, aby ją przegonić.
Kierują się przy tym następującymi zasadami:
- z każdego miejsca na drzewie (liścia lub rozgałęzienia) można
dojść do każdego innego miejsca (bez zawracania) tylko na jeden
sposób; każda mrówka wybiera właśnie taką drogę do miejsca
lądowania biedronki,
- jeżeli w miejscu lądowania biedronki znajduje się mrówka,
biedronka natychmiast odlatuje,
- jeżeli na drodze, od aktualnego położenia mrówki do miejsca
lądowania biedronki, znajdzie się inna mrówka, to ta położona dalej
od biedronki kończy wędrówkę i zostaje w miejscu swojego
aktualnego położenia,
- jeżeli dwie lub więcej mrówek próbuje wejść na to samo rozgałęzienie
drzewa, to robi to tylko jedna mrówka - ta z najmniejszym numerem,
a reszta mrówek pozostaje na swoich miejscach
(liściach lub rozgałęzieniach),
- mrówka, która dociera do miejsca lądowania biedronki, przegania ją
i pozostaje w tym miejscu.
Biedronka jest uparta i znowu ląduje na drzewie.
Wówczas mrówki ponownie ruszają, aby przegonić intruza.
Dla uproszczenia przyjmujemy, że przejście gałązki łączącej
liść z rozgałęzieniem lub łączącej dwa rozgałęzienia, zajmuje
wszystkim mrówkom jednostkę czasu.
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia opis drzewa,
początkowe położenia mrówek oraz miejsca, w których
kolejno siada biedronka,
- dla każdej mrówki znajdzie jej końcowe położenie
i wyznaczy liczbę mówiącą, ile razy przegoniła
ona biedronkę.
Wejście
W pierwszym wierszu standardowego wejścia znajduje się jedna
liczba całkowita , równa łącznej liczbie liści i rozgałęzień w drzewie,
.
Przyjmujemy, że liście i rozgałęzienia są ponumerowane od 1 do .
W kolejnych wierszach są opisane gałązki - w każdym z tych
wierszy są zapisane dwie liczby całkowite i oznaczające,
że dana gałązka łączy miejsca i .
Gałązki pozwalają na przejście z każdego miejsca na drzewie, do
każdego innego miejsca.
W -szym wierszu jest zapisana jedna liczba całkowita ,
i , równa liczbie mrówek patrolujących drzewo.
W każdym z kolejnych wierszy zapisana jest jedna liczba całkowita
z przedziału od 1 do .
Liczba zapisana w wierszu oznacza początkowe położenie
mrówki nr .
W każdym miejscu (liściu lub rozgałęzieniu) może znajdować się co
najwyżej jedna mrówka.
W wierszu zapisana jest jedna liczba całkowita ,
,
mówiąca ile razy biedronka siada na drzewie.
W każdym z kolejnych wierszy zapisana jest jedna liczba całkowita
z zakresu od 1 do .
Liczby te opisują kolejne miejsca, w których siada biedronka.
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy.
W -tym wierszu powinny zostać
zapisane dwie liczby całkowite oddzielone pojedynczym odstępem -
końcowa pozycja -tej mrówki (numer rozgałęzienia lub liścia) i
liczba mówiąca, ile razy przegoniła ona biedronkę.
Przykład
Dla danych wejściowych:
4
1 2
1 3
2 4
2
1
2
2
2
4
poprawną odpowiedzią jest:
1 0
4 2
Autor zadania: Krzysztof Loryś.